Search results for "Hitting time"
showing 3 items of 3 documents
Exceptional Quantum Walk Search on the Cycle
2016
Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk's hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk's random sampling yields an arbitrary speedup in query complexity over the classical random walk's hitting time. In this context, however, the mixing time to prepare the initial uniform state…
First hitting time for a diffusion
2021
In this thesis, we focus our attention on the generation of the first exit time or the first passage time for diffusions in a one-dimensional context.In the first chapter, we present already well-known methods in order to generate such random variables. We particularly introduce the WOMS algorithm. This algorithm permits the generation of an approximation of the time needed by the Brownian motion in order to exit from a given interval.In the second and third chapters, we explain how to extend the previous algorithm in order to deal with diffusions strongly linked to the one-dimensional Brownian motion. We first consider the Ornstein-Uhlenbeck process, and then we consider a wide class of di…
Hitting Time Distributions in Financial Markets
2006
We analyze the hitting time distributions of stock price returns in different time windows, characterized by different levels of noise present in the market. The study has been performed on two sets of data from US markets. The first one is composed by daily price of 1071 stocks trade for the 12-year period 1987-1998, the second one is composed by high frequency data for 100 stocks for the 4-year period 1995-1998. We compare the probability distribution obtained by our empirical analysis with those obtained from different models for stock market evolution. Specifically by focusing on the statistical properties of the hitting times to reach a barrier or a given threshold, we compare the prob…